//Subset Sum
/* Check whether a subset exist with given sum */

#include<iostream>
using namespace std;

int A[] = {3,2,4,19,3,7,13,10,6,11};
int as[sizeof(A)/sizeof(int)+1][100];
int subsum(int i);
int subsum(int i, int j);

int main()
{
	int i;
	cin >> i;
	while(i>=80)
	{
		cout << "\nInvalid value, Please enter again.\n";
		cin >> i;
	}
	cout << "\n" << subsum(i) << "\n";
	return 0;
}

int subsum(int i)
{
	for(int j=0; j<=sizeof(A)/sizeof(int); j++)
	{
		for(int k=0; k<80; k++)
		as[j][k] = -1;
	}
	return subsum(sizeof(A)/sizeof(int), i);
}

int subsum(int i, int j)
{
	if(i==0 || j<0)
	return 0;
	
	if(j == A[i-1])
	return 1;
	
	if(as[i][j] != -1)
	return as[i][j];
	
	as[i][j] = subsum(i-1,j) || subsum(i-1,j-A[i-1]);
	
	return as[i][j];
}
